'''
Created on Dec 12, 2009

@author: claudiugh
'''

class AprioriRulesGenerator(object):

    def __init__(self, db, minsupp, minconf):
        """
        minsupp and minconf is in percent 
        """
        self.db = db 
        self.minsupp = minsupp 
        self.minconf = minconf 
        self.itemset_supp = {}  

    def _compute_support(self, itemset):
        count = 0
        for t in self.db:
            if t & itemset == itemset:
                # the itemset is included in the transaction 
                count += 1 
        return float(count) / float(len(self.db))
    
    def _get_supp(self, itemset):
        if not self.itemset_supp.has_key(itemset): 
            self.itemset_supp[itemset] = self._compute_support(set(itemset))
        return self.itemset_supp[itemset]  

    @classmethod 
    def gen_candidates(cls, itemsets):
        """ 
        itemsets is a list of tuples 
        """
        k = len(itemsets[0])
        candidates = []
        for i in xrange(len(itemsets)):
            ti = itemsets[i]
            for j in xrange(len(itemsets)):
                tj = itemsets[j]
                if ti[:k-1] == tj[:k-1] and ti[k-1] < tj[k-1]:
                    new_set = list(ti)
                    new_set.append(tj[k-1])
                    valid = True 
                    for pos in xrange(len(new_set)):
                        subset = list(new_set)
                        del subset[pos]
                        if not tuple(subset) in itemsets:
                            valid = False
                    if valid:
                        candidates.append(tuple(new_set))
        return candidates 

    def _print_most_frequent(self, freq):
        """
        Used for debug 
        """
        temp = [tuple([k, v]) for k, v in freq.iteritems()]
        temp.sort(key=lambda x: x[1], reverse=True)
        print temp 

    def _get_initial_candidates(self):
        # compute the 1-itemsets 
        freq = {} 
        for transaction in self.db:
            for item in transaction:
                freq.setdefault(item, 0)
                freq[item] += 1
        #self._print_most_frequent(freq)
        candidates = []
        for item in freq:
            if float(freq[item]) / float(len(self.db)) >= self.minsupp: 
                candidates.append(tuple([item]))
        return candidates  

    def _find_freq_itemsets(self):
        """
        Apriori algorithm 
        """
        candidates = self._get_initial_candidates()
        prev_candidates = None 
        while candidates:
            all_candidates = self.gen_candidates(candidates)
            prev_candidates = candidates 
            candidates = []
            for itemset in all_candidates:
                supp = self._get_supp(itemset)
                if supp >= self.minsupp:
                    candidates.append(itemset)
        return prev_candidates 

    def _emit_rule(self, left, right, itemset):
        conf = self._get_supp(itemset) / self._get_supp(left)
        if conf >= self.minconf: 
            self.assoc_rules.append((left, right))

    def _gen_subsets_rec(self, level, top, present, itemset):
        if level == top:
            left_itemset = []
            right_itemset = [] 
            for i in xrange(top): 
                if present[i]: 
                    right_itemset.append(itemset[i])
                else: 
                    left_itemset.append(itemset[i])
            if left_itemset and right_itemset: 
                self._emit_rule(tuple(left_itemset), tuple(right_itemset), itemset)
        else:
            for value in [False, True]: 
                present[level] = value 
                self._gen_subsets_rec(level + 1, top, present, itemset)

    def _gen_subsets(self, itemset):
        """
        Generate all possible subsets for an itemset: 2 ^ N 
        """
        itemset_size = len(itemset)
        present = []
        for i in xrange(itemset_size):
            present.append(False)
        self._gen_subsets_rec(0, itemset_size, present, itemset)
        
    def find_assoc_rules(self):
        freq_itemsets = self._find_freq_itemsets()
        self.assoc_rules = [] 
        for itemset in freq_itemsets: 
            self._gen_subsets(itemset)
        return self.assoc_rules 
        
    @staticmethod 
    def print_assoc_rules(assoc_rules):
        print "There are %d association rules" % len(assoc_rules)
        for rule in assoc_rules: 
            (L, R) = rule 
            print L, ' -> ', R

    
